#include <iostream>
using namespace std;

int a[] = {3, 2, 1, 9, 5, 4, 6, 8, 7, 101, 95, 47};
const int LEN = sizeof(a) / sizeof(int);

void max_heapify(int* A, int i, int len) {
    int left = i * 2 + 1;
    int right = i * 2 + 2;
    int largest = i;

    if (left < len && A[left] > A[i]) {
        largest = left;
    }

    if (right < len && A[right] > A[largest]) {
        largest = right;
    }

    if (largest != i) {
        int t = A[i];
        A[i] = A[largest];
        A[largest] = t;

        max_heapify(A, largest, len);
    }
}

void build_max_heap(int* A) {
    for (int i = (LEN-1) / 2; i >= 0; i--) {
        max_heapify(A, i, LEN);
    }
}

void heap_sort(int* A) {
    build_max_heap(A);
    int len = LEN;
    for (int i = LEN - 1; i > 0; i--) {
        int t = A[i];
        A[i] = A[0];
        A[0] = t;
        len -= 1;
        max_heapify(A, 0, len);
    }
}

void print() {
    for (int i = 0; i < LEN; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

int main() {
    build_max_heap(a);
    print();
    heap_sort(a);
    print();
    return 0;
}
